﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0093_LengthOfLIS : IAlgorithm
    {
        // 300. 最长递增子序列

        // 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
        // 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组[0, 3, 1, 6, 2, 2, 7] 的子序列。

        // 提示：
        //  1 <= nums.length <= 2500
        //  -10^4 <= nums[i] <= 10^4

        // 进阶：
        //  你可以设计时间复杂度为 O(n2) 的解决方案吗？
        //  你能将算法的时间复杂度降低到 O(n log(n)) 吗?


        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 10, 9, 2, 5, 3, 7, 101, 18 };
            //var nums = new int[] { 0, 1, 0, 3, 2, 3 };
            //var nums = new int[] { 7, 7, 7, 7, 7, 7, 7 };
            // 算法执行与打印
            Console.WriteLine(LengthOfLIS(nums));
        }

        // 算法
        public int LengthOfLIS(int[] nums)
        {
            var dp = new int[nums.Length];
            dp[0] = 1;
            int maxans = 1;
            for (int i = 1; i < nums.Length; i++)
            {
                dp[i] = 1;
                for (int j = 0; j < i; j++)
                    if (nums[i] > nums[j])
                        dp[i] = Math.Max(dp[i], dp[j] + 1);
                maxans = Math.Max(maxans, dp[i]);
            }
            return maxans;
        }

        public int LengthOfLIS1(int[] nums)
        {
            int len = 1, n = nums.Length;
            int[] d = new int[n + 1];
            d[len] = nums[0];
            for (int i = 1; i < n; ++i)
                if (nums[i] > d[len])
                    d[++len] = nums[i];
                else
                {
                    // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                    int l = 1, r = len, pos = 0;
                    while (l <= r)
                    {
                        int mid = (l + r) >> 1;
                        if (d[mid] < nums[i])
                        {
                            pos = mid;
                            l = mid + 1;
                        }
                        else
                        {
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            return len;
        }
    }
}
